package com.lw.leetcode.sort.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 1488. 避免洪水泛滥
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/11 12:02
 */
public class AvoidFlood {

    public static void main(String[] args) {
        AvoidFlood test = new AvoidFlood();

        // [-1, -1, 1, 2, -1, -1]
//        int[] arr = {1, 2, 0, 0, 1, 2};

        // []
//        int[] arr = {1, 2, 0, 1, 2};

        // [-1,69,1,1,-1]
        int[] arr = {69,0,0,0,69};

        int[] ints = test.avoidFlood(arr);
        System.out.println(Arrays.toString(ints));
    }

    public int[] avoidFlood(int[] rains) {
        Map<Integer, Integer> map = new HashMap<>();
        TreeMap<Integer, Integer> items = new TreeMap<>();
        int length = rains.length;
        for (int i = 0; i < length; i++) {
            int k = rains[i];
            if (k == 0) {
                items.put(i, 1);
            } else {
                Integer index = map.get(k);
                rains[i] = -1;
                map.put(k, i);
                if (index != null) {
                    Integer key = items.ceilingKey(index);
                    if (key == null) {
                        return new int[0];
                    } else {
                        items.remove(key);
                        rains[key] = k;
                    }
                }
            }
        }
        for (int i = 0; i < length; i++) {
            if (rains[i] == 0) {
                rains[i] = 1;
            }
        }
        return rains;
    }

}
